Date: Wed, 20 Nov 1996 21:43:30 GMT
Server: NCSA/1.5
Content-type: text/html

<!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
<!Converted with LaTeX2HTML 95.1 (Fri Jan 20 1995) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds >
<HEAD>
<TITLE>No Title</TITLE>
</HEAD>
<BODY>
<meta name="description" value="No Title">
<meta name="keywords" value="Home">
<meta name="resource-type" value="document">
<meta name="distribution" value="global">
<P>

<P>
  
<Body bgcolor= #FFF8DC>


<P>
<H2><A NAME=SECTION00001000000000000000> CS 330 (Algorithms) --- Fall 95</A></H2>
<P>
<!WA0><A NAME=tex2html1 HREF="http://cs-www.bu.edu/Home.html">Computer Science Department, 
  Boston University</A>
<P>
<!WA1><IMG  ALIGN=BOTTOM ALT="" SRC="http://www.cs.bu.edu/faculty/gacs/courses/cs330/Home/img1.gif">
 <DL ><DT>Solutions:
<DD>
  Homework: 
  <!WA2><A NAME=tex2html2 HREF="http://cs-www.bu.edu/faculty/gacs/courses/cs330/hw/09-07/09-07.html">1</A>,
  <!WA3><A NAME=tex2html3 HREF="http://cs-www.bu.edu/faculty/gacs/courses/cs330/hw/09-14/09-14.html">2</A>,
  <!WA4><A NAME=tex2html4 HREF="http://cs-www.bu.edu/faculty/gacs/courses/cs330/hw/09-21/09-21.html">3</A>,
  <!WA5><A NAME=tex2html5 HREF="http://cs-www.bu.edu/faculty/gacs/courses/cs330/hw/09-28/09-28.html">4</A>,
  <!WA6><A NAME=tex2html6 HREF="http://cs-www.bu.edu/faculty/gacs/courses/cs330/hw/10-05/10-05.html">5</A>,
  <!WA7><A NAME=tex2html7 HREF="http://cs-www.bu.edu/faculty/gacs/courses/cs330/hw/10-12/10-12.html">6</A>,
 <!WA8><A NAME=tex2html8 HREF="http://cs-www.bu.edu/faculty/gacs/courses/cs330/hw/10-19/10-19.html">7</A>,
 <!WA9><A NAME=tex2html9 HREF="http://cs-www.bu.edu/faculty/gacs/courses/cs330/hw/11-02/11-02.html">8</A>,
 <!WA10><A NAME=tex2html10 HREF="http://cs-www.bu.edu/faculty/gacs/courses/cs330/hw/11-09/11-09.html">9</A>,
 <!WA11><A NAME=tex2html11 HREF="http://cs-www.bu.edu/faculty/gacs/courses/cs330/hw/11-16/11-16.html">10</A>,
 <!WA12><A NAME=tex2html12 HREF="http://cs-www.bu.edu/faculty/gacs/courses/cs330/hw/11-30/11-30.html">11</A>,
 <!WA13><A NAME=tex2html13 HREF="http://cs-www.bu.edu/faculty/gacs/courses/cs330/hw/v1/v1.html">Midterm</A>
<P>
  <DT>Office hours:
<DD> T 3:30-5, W 1:30-3
  <DT>Book:
<DD> Cormen, Leiserson, Rivest: Algorithms.  McGraw-Hill 1990.
  <DT>Topics:
<DD>
  Some commonly used algorithms and data structures.  Analysis from the
point of view of correctness, and the amount of resources used.  Some
of the topics: sorting, recursion, set data structures, dynamic
programming, greedy algorithms, backtracking, shortest path, graph
matching, some algebraic algorithms, NP problems.
  <DT>Prerequisites:
<DD>  CS112, MA293
  <DT>Kind of work required:
<DD> Read the textbook, solve the homework
problems (may involve writing C programs as well as giving
mathematical proofs), participate in the class discussion.
  <DT>Homework:
<DD> given, in general, on Thursday and due in class on
Tuesday 12 days later.  No credit for late homework.
  <DT>Tests:
<DD> a midterm exam, and a final exam (closed book, closed
notes), and one or two unannounced short quizzes.
  For the tests, a single handwritten (&quot;crib&quot;) sheet is permissible.
  <DT>Final grade:
<DD> Approximately, 25% for homework, 25% for the
midterm, 30% for the final, 10% for the quizzes, 10% for class
participation.
  <DT>Information updates:
<DD> on the Worl-wide Web at <BR>
http://cs-www.bu.edu/faculty/gacs/courses/cs330.
  <DT>Tentative more detailed plan of topics:
<DD>
 <DL ><DT>09/05
<DD>
  Intro. Insertion sort. Alg. anal. concepts.
<DT>09/07
<DD>
  Recursion.  Merge sort.
<DT>09/12
<DD>
  Rates of growth.
<DT>09/14
<DD>
  More rates of growth.  Recursive listing of permutations.  Heaps
<DT>09/19
<DD>
  More heaps
<DT>09/21
<DD>
  Quicksort
<DT>09/26
<DD>
  Analysis of randomized Quicksort.
<DT>09/28
<DD>
  Median in exp. linear time.
<DT>10/03
<DD>
  Hashing, with linked lists.
<DT>10/05
<DD>
  Hashing, open adressing.
<DT>10/10
<DD>
  Monday schedule due to Columbus Day.
<DT>10/12
<DD>
  Binary search trees.
<DT>10/12
<DD>
  (Shift everything down) Red-black trees.
<DT>10/17
<DD>
  Dynamic programming.
<DT>10/19
<DD>
  Greedy algorithms.
<DT>10/24
<DD>
  More greedy algorithms.  Graph representation.
<DT>10/26
<DD>
  Breadth-first search.  Depth-first search.
<DT>10/31
<DD>
  Midterm (material up to red-black trees)
<DT>11/02
<DD>
  Eval. of midterm.  Depth-first search.  Topological sort
<DT>11/07
<DD>
  Spanning trees. (Mergeable heaps.)  Shortest paths.
<DT>11/09
<DD>
  Shortest paths cont.  All-pairs shortest paths.
<DT>11/14
<DD>
  Max. flow.
<DT>11/16
<DD>
  Bipartite matching.
<DT>11/21
<DD>
  Branch-and-bound illustrated on the longest path problem.
<DT>11/23
<DD>
  Thanksgiving.
<DT>11/28
<DD>
  Approximation algorithms: vertex cover and set cover.
<DT>11/30
<DD>
  Polynomial complexity, NP problems.
<DT>12/05
<DD>
  NP-complete problems.
<DT>12/07
<DD>
  Shift from above
<DT>12/12
<DD>
  Tba
<P>
 </DL> 
 </DL><HR>
<P><ADDRESS>
Peter Gacs - gacs@cs.bu.edu
</ADDRESS>
</BODY>
